package lc787;

import java.util.*;

public class Lc787_1 {

    public static void main(String[] args) {
        //3
        // [[0,1,100],[1,2,100],[0,2,500]]
        // 0
        // 2
        // 1
        int[][] flights = new int[3][3];
        flights[0][0] = 0;
        flights[0][1] = 1;
        flights[0][2] = 100;
        flights[1][0] = 1;
        flights[1][1] = 2;
        flights[1][2] = 100;
        flights[2][0] = 0;
        flights[2][1] = 2;
        flights[2][2] = 500;
        Lc787_1 solution = new Lc787_1();
        int cheapestPrice = solution.findCheapestPrice(3, flights, 0, 2, 1);
        System.out.println(cheapestPrice);

    }

    int INF = 1000007;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        return bfs(n, flights, src, dst, k);
    }

    private int bfs(int n, int[][] flights, int src, int dst, int k) {
        // 整理题目给定的flights，转换成每个节点的子节点有哪些
        Map<Integer, List<int[]>> g = new HashMap<>(n*2);
        for(int i = 0; i < n; i++){
            g.put(i, new ArrayList<>());
        }
        // 遍历航线，给g填充路径，下标为开始路径坐标点，内容为可走的路线。
        // 例如g[0]=[[1,100],[2,500]]] g[1]=[[2,200]]
        // 表示在src为0时有两条路线，分别为1和2，费用是100和500
        //  src为1时有1条路径，分别为2，费用为200
        for(int[] flight: flights){
            g.get(flight[0]).add(new int[]{flight[1], flight[2]});
        }

        // 表示src到i到最小价格，填充一个比较大的数字，必须在答案范围外，但是因为比最小值，不建议选负数。
        int[] ans = new int[n];
        Arrays.fill(ans, INF);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{src, 0});
        // 退出条件加上 k 的限制
        while(!queue.isEmpty() && k + 1 > 0){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                // poll[0] 目前的坐标
                // poll[1] 存储的是src到当前位置的价格
                int[] poll = queue.poll();
                // 从g中获取当前下标的所有路线
                for(int[] path: g.get(poll[0])){
                    // 计算src到上一级路径的价格+当前路径价格的总费用 也就是当前路径下src到当前路径的价格
                    int currPathPrice = poll[1] + path[1];
                    // 剪枝1，当前价格少于之前当前路径的价格，且小于 之前记录的到最终记录的价格
                    // 说明当前价格是src到当前点，之前的所有路径的最低价，则替换
                    if(currPathPrice < ans[path[0]] && currPathPrice < ans[dst]){
                        ans[path[0]] = currPathPrice;
                        // 剪枝2，如果路径已经到了 dst 了，则退出，否则在队列插入当前的价格，继续下个循环
                        if(path[0] != dst){
                            queue.offer(new int[]{path[0], currPathPrice});
                        }
                    }
                }
                // for(int[] path: g[poll[0]]){
                //     // 计算src到上一级路径的价格+当前路径价格的总费用 也就是当前路径下src到当前路径的价格
                //     int currPathPrice = poll[1] + path[1];
                //     // 剪枝1，当前价格少于之前当前路径的价格，且小于 之前记录的到最终记录的价格
                //     // 说明当前价格是src到当前点，之前的所有路径的最低价，则替换
                //     if(currPathPrice < ans[path[0]] && currPathPrice < ans[dst]){
                //         ans[path[0]] = currPathPrice;
                //         // 剪枝2，如果路径已经到了 dst 了，则退出，否则在队列插入当前的价格，继续下个循环
                //         if(path[0] != dst){
                //             queue.offer(new int[]{path[0], currPathPrice});
                //         }
                //     }
                // }
            }
            k--;
        }

        return ans[dst] >= INF ? -1 : ans[dst];
    }

    private int bfs1(int n, int[][] flights, int src, int dst, int k) {
        // 整理题目给定的flights，转换成每个节点的子节点有哪些

        List<int[]>[] g = new List[n];
        for(int i = 0; i < n; i++){
            g[i] = new ArrayList<>();
        }
        // 遍历航线，给g填充路径，下标为开始路径坐标点，内容为可走的路线。
        // 例如g[0]=[[1,100],[2,500]]] g[1]=[[2,200]]
        // 表示在src为0时有两条路线，分别为1和2，费用是100和500
        //  src为1时有1条路径，分别为2，费用为200
        for(int[] flight: flights){
            g[flight[0]].add(new int[]{flight[1], flight[2]});
        }

        // 表示src到i到最小价格，填充一个比较大的数字，必须在答案范围外，但是因为比最小值，不建议选负数。
        int[] ans = new int[n];
        Arrays.fill(ans, INF);
        Queue<int[]> queue = new LinkedList<>();
        // queueData[0] 目前的坐标
        // queueData[1] 存储的是src到当前位置的价格
        queue.offer(new int[]{src, 0});
        // 退出条件加上 k 的限制
        while(!queue.isEmpty() && k + 1 > 0){
            int size = queue.size();
            for(int i = 0; i < size; i++){

                int[] poll = queue.poll();
                for(int[] path: g[poll[0]]){
                    int distance = poll[1] + path[1];
                    // 剪枝1，小于 i 之前记录的最小值，且小于 dst 之前记录的最小值
                    if(distance < ans[path[0]] && distance < ans[dst]){
                        ans[path[0]] = distance;
                        // 剪枝2，到 dst 了就不用继续往下了
                        if(path[0] != dst){
                            queue.offer(new int[]{path[0], distance});
                        }
                    }
                }
            }
            k--;
        }

        return ans[dst] >= INF ? -1 : ans[dst];
    }

}
